Reed-Solomon codes are commonly used error correction codes. Their widespread applications include magnetic and optical data storage, wireline and wireless communications, and satellite communications. A Reed-Solomon code (n,k) over a finite field GF(q) satisfies n<q and achieves the maximally separable distance, i.e., d=n−k+1. The Berlekamp-Massey method efficiently decodes up to half minimum distance with complexity O(dn). The method can be clearly divided into three operation stages. The first stage performs syndrome computation, which takes n cycles. The second stage computes the error locator polynomial and the scratch polynomial, which takes d cycles. (In practice, the code rate is high and thus the minimum distance d is much smaller than the code length n.) The third stage performs Chien search and error evaluation, which costs n cycles. The total number of cycles is 2n+d. It would be desirable to reduce the latency of the whole decoding process while keeping both power consumption and decoding failure rate approximately the same. Such improvements would be particularly attractive for on-the-fly applications where a low latency is desirable.